package Tree;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Stack;

class TreeNode{
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
     this.val = val;
     this.left = left;
     this.right = right;
    }
}
// 前序遍历
//class Solution1 {
//    public List<Integer> preorderTraversal(TreeNode root) {
//        List<Integer> res = new ArrayList<>();
//        if(root == null){
//            return res;
//        }
//        Stack<TreeNode> stack = new Stack<>();
//        stack.push(root);
//        while(!stack.isEmpty()){
//            TreeNode node = stack.pop();
//            res.add(node.val);
//            if(node.right != null){
//                stack.push(node.right);
//            }
//            if(node.left != null){
//                stack.push(node.left);
//            }
//        }
//        return res;
//    }
//}

// 中序遍历
//class Solution1 {
//    public List<Integer> inorderTraversal(TreeNode root) {
//        List<Integer> res = new ArrayList<>();
//        if(root == null){
//            return res;
//        }
//        Stack<TreeNode> stack = new Stack<>();
//        TreeNode cur = root;
//        while(cur != null || !stack.isEmpty()){
//            if(cur != null){
//                stack.push(cur);
//                cur = cur.left;
//            }else{
//                cur = stack.pop();
//                res.add(cur.val);
//                cur = cur.right;
//            }
//        }
//        return res;
//    }
//}

// 后序遍历
class Solution1 {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if(root == null){
            return res;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while(!stack.isEmpty()){
            TreeNode node = stack.pop();
            res.add(node.val);
            if(node.left != null){
                stack.push(node.left);
            }
            if(node.right != null){
                stack.push(node.right);
            }
        }
        Collections.reverse(res);
        return res;
    }
}